//
//  Problem1140.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/1.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1140. 石子游戏 II
 亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
 游戏一直持续到所有石子都被拿走。
 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

 示例：
     输入：piles = [2,7,9,4,4]
     输出：10
     解释：
     如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
     如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
     所以我们返回更大的 10。
  
 提示：
     1 <= piles.length <= 100
     1 <= piles[i] <= 10 ^ 4
 */
@objcMembers class Problem1140: NSObject {
    func solution() {
        print(stoneGameII([2,7,9,4,4]))
    }
    
    /*
     动态规划
     1: 创建一个数组 dp[len][len]
     2: dp[i][m]：i～len个数，在m的情况下最大值
     3: dp[i][m] = max()
        for j in (1...2*m):
            if i + j >=  len {
                piles[j] + sum(i+j ... len)
            } else {
                piles[j] + sum(i+j ... len) - dp[i+1][max(j,m)](这是后面那个人的选择的最大值)
            }
     */
    func stoneGameII(_ piles: [Int]) -> Int {
        if piles.count == 1 {               // 特例：只有一堆
            return piles[0]
        } else if piles.count == 2 {        // 特例：只有两堆
            return piles[0] + piles[1]
        }
        
        var dp = Array(repeating: Array(repeating: Int.min, count: piles.count+1), count: piles.count)
        for i in (0..<piles.count).reversed() {
            dp[i][piles.count] = i == piles.count - 1 ? piles[i] : piles[i] + dp[i + 1][piles.count]
            dp[piles.count - 1][i] = piles.last ?? 0
        }
        let value = getSumDP(piles, &dp, 0, 1)
        return value
    }
    
    func getSumDP(_ piles: [Int], _ dp: inout [[Int]], _ start: Int, _ M: Int) -> Int {
        if M > piles.count {       // 说明可以一次性把所有的都拿走
            return dp[start][piles.count]
        }
        
        if dp[start][M] != Int.min {
            return dp[start][M]
        }
        
        let n = min(2*M, piles.count - start)
        
        for j in 1...n {
//            dp[start][M] = max(dp[start][M], getSumIJ(piles, start, start+j-1) + dp[start+j][piles.count-1] - getSumDP(piles, &dp, start + j, max(j, M)))
            // => 下面👇
            if start + j >= piles.count {
                dp[start][M] = max(dp[start][M], dp[start][piles.count])
            } else {
                dp[start][M] = max(dp[start][M], dp[start][piles.count] - getSumDP(piles, &dp, start + j, max(j, M)))
            }
            
        }
        return dp[start][M]
    }
    
    func getSumIJ(_ piles: [Int], _ start: Int, _ end: Int) -> Int {
        if start == end {
            return piles[start]
        } else {
            var value = 0
            for i in start...end {
                value += piles[i]
            }
            return value
        }
    }
}
